The present invention relates to a method for performing matrix multiplication and more specifically, to a method for performing large-scale sparse matrix-matrix multiplication based on a midpoint approach.
Sparse matrix multiplication is one of the common problems in linear algebra, with important application to recent fields like data analytics. In fact, it comes up often in machine learning, graph analytics and data mining. For instance, graph processing has become an important component of bioinformatics, social network analysis, traffic engineering, etc. With graphs getting larger and queries getting more complex, there is a need for graph analysis frameworks to help users extract the information they need with minimal computational effort. Therefore, improving the speed and scalability of sparse matrix-matrix multiplication algorithm for large matrices is of paramount importance for industries and for the scientific community.
Nowadays, the multiplication of sparse matrices is processed using algorithms designed for dense matrices. The leading methodology to multiply dense matrices is the Shared and Remote memory access based Universal Matrix Multiplication Algorithm (SRUMMA). The main drawback of the SRUMMA algorithm for sparse matrices is the O(√{square root over (P)}) communication steps as well as the O(√{square root over (P)}) logistic, wherein P is the number of processes handling the multiplication, i.e. inter-process communication does not decrease linearly or essentially linearly with increasing number of processes. This parallel behavior prevents the processing of large-scale sparse matrices, irrespective of the available computational power. Although a large number of efforts were made in the last years, no algorithm for sparse matrices goes beyond the (√{square root over (P)}) scalability limit.